package 路径总和ii;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution {
    /*
    给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
    叶子节点 是指没有子节点的节点。
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        // 递归
        // 1.参数：根节点，当前的sum值，从root到当前节点的path，结果路径集
        // 返回值：因为需要遍历整颗树，且不需要处理递归的返回值，需要返回值为 void
        // 2.终止条件：碰到叶子节点时
        // 3.单层递归逻辑：因为不需要处理根节点，所以左右子树处理顺序无所谓。先处理左子树，当遇到叶子节点的时
        // 需要判断当前的count值是否符合要求（采用从targetSum一直减为0的方法），如果符合要求就将该路径加入到结果集中
        if (root == null)
            return Collections.emptyList();
        List<List<Integer>> result = new ArrayList<>();
        findPath(root, targetSum - root.val, new ArrayList<>(Arrays.asList(root.val)), result);
        return result;
    }

    public void findPath(TreeNode root, int count, List<Integer> path, List<List<Integer>> result) {
        if (root.left == null && root.right == null) {
            if (count == 0) {
                // 需要保存该路径
                ArrayList<Integer> newPath = new ArrayList<>(path);
                result.add(newPath);
            }
            return;
        }
        // 左
        if (root.left != null) {
            path.add(root.left.val);
            count -= root.left.val;
            findPath(root.left, count, path, result);
            path.remove(path.size() - 1); // 回溯
            count += root.left.val; // 回溯
        }
        // 右
        if (root.right != null) {
            path.add(root.right.val);
            count -= root.right.val;
            findPath(root.right, count, path, result);
            path.remove(path.size() - 1); // 回溯
            count += root.right.val; // 回溯
        }
    }
}
